package dynamic;

public class LongestSubstring {

    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = s.charAt(0) == s.charAt(1) ? 1 : 2;
        for (int i = 2; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                dp[i] = dp[i - 1];
            } else {
                if (s.charAt(i-1) == s.charAt(i-2)) {
                    dp[i] = Math.max(max(dp, 0, i -1), 2);
                } else {
                    dp[i] = dp[i-1] + 1;
                }
            }
        }
        return dp[n - 1];
    }
    public int max(int[] array, int start, int end) {
        int max = array[start];
        for (int i = 1; i < end + 1; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        LongestSubstring longestSubstring = new LongestSubstring();
        System.out.println(longestSubstring.lengthOfLongestSubstring("abcabcbb"));
    }
}
